// https://leetcode.cn/problems/beautiful-arrangement/

// 题干：假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始）
//      只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
//      perm[i] 能够被 i 整除
//      i 能够被 perm[i] 整除
//      给你一个整数 n ，返回可以构造的 优美排列 的 数量 。

// 示例：输入：n = 2
//       输出：2

// 碎语：在全排列问题上的剪枝，如果符合题意，则放到path，如果不符合则跳过

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    bool check[16];
    int ret;
    int n; // n是perm所要求添加的数量
public:
    int countArrangement(int _n)
    {
        ret = 0, n = _n;
        memset(check, 0, sizeof(check));
        dfs(1); // 下标从开始，那就传入1

        return ret;
    }

    void dfs(int pos) // dfs表示给一个数组的pos位置上添一个合法数字
    {
        if (pos == n + 1){
            ret++;
            return ;
        }

        for (int i = 1 ; i <= n ; i++){
            if (!check[i] && (i % pos == 0 || pos % i == 0)){
                check[i] = true;
                dfs(pos + 1);

                check[i] = false; // 回溯
            }
        }
    }
};

int main()
{
    Solution sol;

    cout << sol.countArrangement(2) << endl;

    return 0;
}